package com.lims.algorithm.algset;

import java.util.Scanner;
/*
 * 青蛙跳台阶问题，一只青蛙要跳上n层高的台阶，一次能跳一级，也可以跳两级，请问这只青蛙有多少种跳上这个n层高台阶的方法？
 */
public class Rabbit {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		System.out.print("输入参数：");
		int n = sc.nextInt();
		while (n != 0) {
			if (n >= 0){
				System.out.println("递归法求跳法有......" + recursion(n));
				System.out.println("迭代法求跳法有......" + iterator(n));
				System.out.println("排列组合法求跳法有：" + combination(n));
				System.out.println("递归求阶乘：" + fact(n));
				System.out.println("迭代求阶乘:" + factIteractor(n));
			} else {
				System.out.print("输入参数小于0，重新输入：");
			}
			System.out.print("输入参数：");
			n = sc.nextInt();
		}
	}
	
	/*
	 * 递归法 求跳法
	 */
	public static int recursion(int n) {
		if(n <= 0) {
			return 0;
		} else if(n == 1 || n==2) {
			return n;
		} else {
			return recursion(n-1) + recursion(n-2);
		}
	}
	
	/*
	 * 迭代法（公式同递归法）
	 */
	public static long iterator(int n) {
		long fn1 = 1;
		long fn2 = 2;
		long fn =0;
		for(int i = 3; i <= n; i++) {
			fn = fn1 + fn2;
			fn1 = fn2;
			fn2 = fn;
		}
		return fn;
	}
	
	/*
	 * 排列组合法 （运用组合） 
	 */
	public static long combination(int n) {
		long total = 0;
		//x为跳两步， y为跳1步， x必然散落区间为 0到n/2
		//公式 z = x + y; n = 2x + y;     在z上对x求组合 ，z和y 用x和n表示，对x 在区间里遍历
		for(int x = 0; x < n/2 +1; x++) {
			//total += fact(n-x)/fact(n-2*x)/fact(x); //会存在栈溢出
			total += factIteractor(n-x)/factIteractor(n-2*x)/factIteractor(x);
		}
		return total;
	}
	//递归求阶乘
	public static long fact(int n) {
		if(n == 1)
			return n;
		return n * fact(n -1);
	}
	//迭代求阶乘
	public static long factIteractor(int n) {
		long result = 1;
		for(int x = 1; x <=n; x++) {
			result *= x;
		}
		return result;
	}

}
